﻿#include <iostream>
#include <string>
#include <vector>
#include <algorithm>
#include <unordered_map>
using namespace std;

class Solution
{
public:
	bool isUnique(string astr)
	{
		// 利⽤鸽巢原理来做的优化
		if (astr.size() > 26) return false;
		int bitMap = 0;
		for (auto ch : astr)
		{
			int i = ch - 'a';
			// 先判断字符是否已经出现过
			if (((bitMap >> i) & 1) == 1) return false;
			// 把当前字符加⼊到位图中
			bitMap |= 1 << i;
		}
		return true;
	}
};
//191 位1 的个数
class Solution {
public:
	int hammingWeight(int n)
	{
		int count = 0;
		for (int i = 0; i < 32; i++)
		{
			if ((n >> i) & 1 == 1)
			{
				count++;
			}
		}
		return count;
	}
};

//338 比特位计数
class Solution {
public:
	int Countones(int n)
	{
		int count = 0;
		for (int i = 0; i < 32; i++)
		{
			if ((n >> i) & 1 == 1)
			{
				count++;
			}
		}
		return count;
	}
	vector<int> countBits(int n)
	{
		vector<int> ret(n + 1);
		for (int i = 0; i <= n; i++)
		{
			ret[i] = Countones(i);
		}

		return ret;
	}
};

//338 汉明距离
class Solution {
public:
	int hammingDistance(int x, int y)
	{
		//这两个数字对应二进制位不同的位置的个数
		int count = 0;
		for (int i = 0; i < 32; i++)
		{
			int n = (x >> i) & 1;
			int m = (y >> i) & 1;
			if ((n == 1 && m == 0) || (n == 0 && m == 1))
			{
				count++;
			}
		}
		return count;
	}
};

class Solution {
public:
	int singleNumber(vector<int>& nums)
	{
		int value = 0;
		for (auto e : nums)
		{
			value ^= e;
		}
		return value;
	}
};

class Solution {
public:
	vector<int> singleNumber(vector<int>& nums) {
		std::sort(nums.begin(), nums.end());
		size_t i = 0;
		vector<int> v;

		while (i < nums.size()) {
			size_t j = i + 1;

			// 检查是否越界
			if (j >= nums.size() || nums[i] != nums[j]) {
				v.push_back(nums[i]);
				i++;  // 只移动一位
			}
			else {
				i += 2;  // 跳过匹配的成对数字
			}

			// 找到两个单独出现的数字后，停止循环
			if (v.size() == 2) {
				break;
			}
		}

		return v;
	}
};

class Solution {
public:
	bool isUnique(string astr)
	{
		// 利⽤鸽巢原理来做的优化
		if (astr.size() > 26) return false;
		int bitmap = 0;
		for (auto ch : astr)
		{
			int i = ch - 'a';

			// 为 1 说明已经存在过了
			if ((bitmap >> i) & 1 == 1)
				return false;

			//将n的二进制的第i位改为1 把当前字符加⼊到位图中
			bitmap |= (1 << i);
		}
		return true;
	}
};


class Solution {
public:
	//hash
	int missingNumber(vector<int>& nums)
	{
		int ret = 0;
		unordered_map<int, int> hash;
		for (auto e : nums)
		{
			hash[e]++;
		}
		for (int i = 0; i <= nums.size(); i++)
		{
			if (!hash[i])
			{
				ret = i;
			}
		}
		return ret;
	}
};

class Solution {
public:
	//高斯公式
	int missingNumber(vector<int>& nums)
	{
		int n = nums.size();
		int ret = ((0 + n) * (n + 1)) / 2;
		for (auto x : nums)
		{
			ret -= x;
		}
		return ret;
	}
};

class Solution {
public:
	//异或消消乐
	int missingNumber(vector<int>& nums)
	{
		int n = nums.size();
		int ret = 0;
		for (auto x : nums)
		{
			ret ^= x;
		}
		for (int i = 0; i <= n; i++)
		{
			ret ^= i;
		}
		return ret;
	}
};

class Solution {
public:
	int singleNumber(vector<int>& nums)
	{
		int ret = 0;
		for (int i = 0; i < 32; i++)
		{
			int sum = 0;
			for (auto x : nums)
				if (((x >> i) & 1) == 1)
					sum++;
			sum %= 3;
			if (sum == 1) ret |= 1 << i;
		}

		return ret;

	}
};
class Solution {
public:
	vector<int> missingTwo(vector<int>& nums)
	{
		//1.将所有的数异或在一起
		int tmp = 0;
		for (auto x : nums) tmp ^= x;
		for (int i = 1; i <= nums.size() + 2; i++) tmp ^= i;

		//2.找到tmp中，比特位上为1的那一位
		int x = 0;
		for (int i = 0; i < 32; i++)
		{
			if ((tmp >> i) & 1 == 1)
			{
				x = i;
				break;
			}
		}

		//3.根据x位的不同，划分两类异或
		//用 b 来存这一位为1的 用 a 来存这一位为0的 
		int a = 0, b = 0;
		for (auto e : nums)
		{
			if (((e >> x) & 1) == 1) b ^= e;
			else a ^= e;
		}
		for (int i = 1; i <= nums.size() + 2; i++)
		{
			if (((i >> x) & 1)) b ^= i;
			else a ^= i;
		}

		return { a ,b };
	}
};